package cn.datastruct.test;

import java.util.Stack;

import static cn.datastruct.test.CalculatorDemo.priority;
import static cn.datastruct.test.CalculatorDemo.recognize;

/*
*   中缀表达式转后缀表达式思路;
*       1、定义两个辅助栈，一个用来存储数字和操作符，一个用来存储符号
*       2、从左到右开始扫描中缀表达式式
*           2.1、数字则压入数字栈
*           2.2、当扫描到符号
*               2.2.1、如果符号栈为空，则压栈
*               2.2.2、符号栈不为空
*               2.2.2.1、如果当前符号栈中运算符的优先级大于等于待压入栈的符号优先级，则出栈
*               2.2.2.1、如果当前符号栈中运算符的优先级小于待压入栈的符号优先级，则入栈
*       3、当扫描完毕后，将符号栈中的元素压入到前一个栈
* */
public class PolishMBDemo {
    public static void main(String[] args) {
        Stack<String> valueStack = new Stack<String>();
        Stack<Character> operateStack = new Stack<Character>();

        //输入字符串
//        Scanner sc = new Scanner(System.in);
//        String s = sc.nextLine();
        String s =  new StringBuilder("3-2*3+2").reverse().toString();
        String str = "";//用来拼接多位数
        int length = s.length();
        char ch = '0';
        for (int i = 0; i < length; i++) {
            ch = s.charAt(i);
            if(recognize(ch)){//当扫描到符号
                if(str.length() != 0){
                    valueStack.push(str);
                    str = "";
                }
                if(operateStack.empty()){//如果符号栈为空，则压栈
                    operateStack.push(ch);
                }else if(priority(operateStack.peek()) >= priority(ch)){//如果当前符号栈中运算符的优先级大于等于待压入栈的符号优先级，则出栈
                    do {
                        valueStack.push(Character.toString(operateStack.pop()));
                    }while (operateStack.size() > 0 && priority(operateStack.peek()) >= priority(ch));
                    operateStack.push(ch);
                }else if(priority(operateStack.peek()) < priority(ch)){//如果当前符号栈中运算符的优先级小于待压入栈的符号优先级，则入栈
                    operateStack.push(ch);
                }
            }else {
                str += ch;
            }
        }
        valueStack.push(str);//结尾为数字
        while(!operateStack.empty()){
            valueStack.push(Character.toString(operateStack.pop()));
        }
        System.out.printf("%s",s+"的后缀表达式为");
        while (!valueStack.empty()){
            System.out.printf("%s\t",valueStack.pop());
        }

    }
}
